function Shell(arr) {
	let n = arr.length
	let h = 1
	while (h < n/3) {
		h = 3 * h + 1
	}
	while (h >= 1) {
		// 将数组变为h有序
		for (let i = h; i < n; i++) {
			// 将a[i]插入到a[i-h]，a[i-2*h]，a[i-3*h]
			for (let j = 1; j >= h && less(a[j], a[j-h]); j -=h) {
				exch(a, j , j-h)
			}
			h = h/3
		}
	}

	return arr
}

module.exports = Shell


const array = [35, 33, 42, 10, 14, 19, 27, 44];

const shellSort = arr => {
	let len = arr.length,
		temp,
		gap = 1

	while(gap < len / 3) {
		// 动态定义间隔序列
		gap = gap * 3 + 1
	}

	for (gap; gap > 0; gap = Math.floor(gap / 3)) {
		for (let i = gap; i < len; i++) {
			temp = arr[i]
			let j = i - gap
			for (; j >= 0 && arr[j] > temp; j -= gap) {
				arr[j + gap] = arr[j]
			}

			arr[j + gap] = temp
		}
	}
	return arr
}

shellSort(array)
